package class05;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;


public class Code03_TreeMaxWidth {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	/**
	 * 	宽/广度优先遍历 BFS
	 */
	public static void BFS(Node head){
		if (head == null){
			return;
		}



		Queue<Node> queue = new LinkedList<>();

		queue.add(head);
		while (!queue.isEmpty()){
			Node cur = queue.poll(); // 弹出首节点 并打印
			System.out.println(cur.value);
			if (cur.left != null){ // 先左后右
				queue.add(cur.left);
			}
			if (cur.right != null){
				queue.add(cur.right);
			}
		}
	}





	/* ------------------------------------------------ */

	/**
	 * 求最大宽度
	 */

	public static int getMaxWidthHash(Node head){ //-----------这个方法根本没听懂啥呀
		if (head == null){
			return 0;
		}

		Queue<Node> queue = new LinkedList<>();
		queue.add(head);

		HashMap<Node, Integer> levelMap = new HashMap<>(); // 存放该节点在哪一层
		levelMap.put(head, 1);
		int curLevel = 1; //当前在二叉树的 层
		int curLevelNodes = 0; //当前层的节点数 初始值为0
		int max = Integer.MIN_VALUE; //该层节点的最大节点数
		while (!queue.isEmpty()){
			Node cur = queue.poll();
			int curNodeLevel = levelMap.get(cur); // 当前节点所在层
			if (curNodeLevel == curLevel){ // 相等说明在统计该层节点的数量
				curLevelNodes++;
			} else { // 不相等说明上一层已经收集完毕
				max = Math.max(max, curLevelNodes); //上一层的节点数可用来更新max了
				curLevel++; //转到下一层
				curLevelNodes = 1;
			}
			//转到下一层后，把左孩子右孩子放入队列，并且当前节点所在层+1
			if(cur.left != null){
				levelMap.put(cur.left, curNodeLevel+1);
				queue.add(cur.left);
			}
			if (cur.right != null){
				levelMap.put(cur.right, curNodeLevel+1);
				queue.add(cur.right);
			}
		}

		return Math.max(max, curLevelNodes);
	}






	public static int getMaxWidth(Node head) { //-------- 这个没讲到，也没看懂
		if (head == null) {
			return 0;
		}
		int maxWidth = 0;
		int curWidth = 0;
		int curLevel = 0;
		HashMap<Node, Integer> levelMap = new HashMap<>();
		levelMap.put(head, 1);
		LinkedList<Node> queue = new LinkedList<>();
		queue.add(head);
		Node node = null;
		Node left = null;
		Node right = null;
		while (!queue.isEmpty()) {
			node = queue.poll();
			left = node.left;
			right = node.right;
			if (left != null) {
				levelMap.put(left, levelMap.get(node) + 1);
				queue.add(left);
			}
			if (right != null) {
				levelMap.put(right, levelMap.get(node) + 1);
				queue.add(right);
			}
			if (levelMap.get(node) > curLevel) {
				curWidth = 0;
				curLevel = levelMap.get(node);
			} else {
				curWidth++;
			}
			maxWidth = Math.max(maxWidth, curWidth);
		}
		return maxWidth;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
